package imooc_math;
//并查集：能很好地解决网络中两个节点是否连接的问题
public class UF1 {
	//每一个连接在一起的组都有同样的一个id号
	public int[] id;
	public int count;
	public UF1(int n){
		count = n;
		id=new int[n];
		for(int i=0;i<n;i++){
			id[i] = i;
		}
	}
	//让p跟q所在的组的所有数的id都相同
	public void union(int p,int q){
		int pid = find(p);
		int qid = find(q);
		if(pid == qid){
			return;
		}
		for(int i=0;i<count;i++){
			if(id[i] == pid){
				id[i] = qid; 
			}
		}
	}
	//Quick find 时间复杂度：O(n)
	public int find(int p){
		return id[p];
	}
	public boolean isConnected(int p,int q){
		return id[p] == id[q];
	}
}
